class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size(), ret = 1;
        vector<int> f(n, 1), g(n, 1);
        //以i位置元素为结尾的子序列，最后一个位置呈现上升/下降趋势的最长摆动序列的长度
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                    f[i] = max(g[j] + 1, f[i]);
                else if(nums[j] > nums[i])
                    g[i] = max(f[j] + 1, g[i]);
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};